package 链表;

public class Solution10 {
    //https://www.nowcoder.com/practice/02bf49ea45cd486daa031614f9bd6fc3
    public ListNode oddEvenList1 (ListNode head) {
        //思路：遍历值创建值对应新的节点链表
        if(head == null) {
            return null;
        }
        ListNode ret = new ListNode(head.val);
        ListNode tail = ret;
        ListNode cur1 = head;
        ListNode cur2 = head.next;
        while (cur1 != null && cur1.next != null && cur1.next.next != null) {
            tail.next = new ListNode(cur1.next.next.val);
            tail = tail.next;
            cur1 = cur1.next.next;
        }
        while (cur2 != null && cur2.next != null && cur2.next.next != null) {
            tail.next = new ListNode(cur2.next.next.val);
            tail = tail.next;
            cur2 = cur2.next.next;
        }
        return ret;
    }
    public ListNode oddEvenList (ListNode head) {
        //题解：
        //思路：链表往前维护
        ListNode dummy1 = new ListNode(-1);
        ListNode dummy2 = new ListNode(-1);
        ListNode prev1 = dummy1;
        ListNode prev2 = dummy2;
        int index = 1;
        ListNode cur = head;
        while (cur != null) {
            if(index % 2 == 1) {
                prev1.next = cur;
                prev1 = prev1.next;
            }else {
                prev2.next = cur;
                prev2 = prev2.next;
            }
            cur = cur.next;
            index++;
        }
        prev2.next = null;
        prev1.next = dummy2.next;
        return dummy1.next;
    }
}
